The diophantine problem for addition and divisibility for subrings of rational functions over finite fields

Authors

DOI:

https://doi.org/10.22199/issn.0717-6279-2020-03-0045

Keywords:

Positive-existential definability, Finite field of odd characteristic

Abstract

It is shown that the positive existential theory of the structure ℱS = (S−1F[t];=,F, 0, 1,+, |, f ↦ tf), where f tf is the multiplication by t map, S is non-empty a finite set of irreducible polynomials, and F is a finite field of odd characteristic, is undecidable.

Author Biography

Carlos Martínez-Ranero, Universidad de Concepción.

Dept. de Matemática.

References

A. P. Beltyukov, “Decidability of the universal theory of natural numbers with addition and divisibility”, Journal of soviet mathematics, vol. 14, no. 5, pp. 1436–1444, Nov. 1980, doi: 10.1007/BF01693974

L. Cerda-Romero and C. Martínez-Ranero, “The diophantine problem for addition and divisibility over subrings of the rationals”, The journal of symbolic logic, vol. 82, no. 3, pp. 1140–1149, Sep. 2017, doi: 10.1017/jsl.2016.64

A. C. Pheidas, “The diophantine problem for addition and divisibility in polynomial rings (Decidability, undecidability)”, Ph. D. Thesis, Purdue University, 1985. [On line]. Available: https://bit.ly/3cruCUp

T. Pheidas, “Diophantine undecidability for addition and divisibility in polynomial rings”, Fundamenta mathematicae, vol. 182, no. 3, pp. 205–220, 2004, doi: 10.4064/fm182-3-2

H. Kornblum and E. Landau, “Über die primfunktionen in einer arithmetischen progression”, Mathematische zeitschrift, vol. 5, no. 1-2, pp. 100–111, Mar. 1919, doi: 10.1007/BF01203156

H. W. Lenstra, “On Artins conjecture and Euclids algorithm in global fields”, Inventiones mathematicae, vol. 42, no. 1, pp. 201–224, 1977, doi: 10.1007/BF01389788

L. Lipshitz, “Undecidable existential problems for addition and divisibility in algebraic number rings. II”, Proceedings of the American Mathematical Society, vol. 64, no. 1, pp. 122–128, Jan. 1977, doi: 10.1090/S0002-9939-1977-0536659-5

L. Lipshitz, “The Diophantine problem for addition and divisibility”, Transactions of the American Mathematical Society, vol. 235, pp. 271–283, 1978, doi: 10.1090/S0002-9947-1978-0469886-1

L. Lipshitz, “Undecidable existential problem for addition and divisibility in algebraic number rings”, Transactions of the American Mathematical Society, vol. 241, pp. 121-128, 1978, doi: 10.1090/S0002-9947-1978-0536658-9

J. Robinson, “Definability and decision problems in arithmetic”, Journal of symbolic logic, vol. 14, no. 2, pp. 98–114, Jun. 1949, doi: 10.2307/2266510

Published

2020-06-03

How to Cite

[1]
L. A. Cerda-Romero and C. Martínez-Ranero, “The diophantine problem for addition and divisibility for subrings of rational functions over finite fields”, Proyecciones (Antofagasta, On line), vol. 39, no. 3, pp. 721-735, Jun. 2020.

Issue

Section

Artículos